package alg2_bagQueueStack;

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

import java.util.Iterator;
import java.util.Queue;

//使用链表实现队列
public class Test3_QueueWithLink<Item> implements Iterable<Item>{

    //指向最早添加的节点的链接
    private Node first;
    //指向最近添加的节点的链接
    private Node last;
    //队列中的元素数量
    private int N;
    //节点的嵌套类
    private class Node {
        Item item;
        Node next;
    }

    public boolean isEmpty() {
        return first == null;
    }
    public int size(){
        return N;
    }

    //向表尾部添加元素
    public void enqueue(Item item){
        Node oldLast = last;
        last = new Node();
        last.item = item;
        last.next = null;
        if (isEmpty()){
            first = last;
        }else{
            oldLast.next = last;
        }
        N++;
    }

    //从表头删除元素
    public Item dequeue(){
        Item item = first.item;
        first = first.next;
        if (isEmpty()) last = null;
        N--;
        return item;
    }


    @Override
    public Iterator<Item> iterator() {
        return null;
    }
}

class TestQueue{
    public static void main(String[] args) {
        //创建一个队列并操作字符串入列和出列
        Test3_QueueWithLink<String> q = new Test3_QueueWithLink<String>();
        while (!StdIn.isEmpty()){
            String item = StdIn.readString();
            if (!item.equals("-")){
                q.enqueue(item);
            }else if(!q.isEmpty()){
                StdOut.print(q.dequeue() + " ");
            }
        }
        StdOut.println("(" + q.size() + " left on queue)");
    }
}